//
// Created by Acer on 2/21 021.
//
#include <jni.h>
#include <string>
#include <android/log.h>
#include <queue>
#include <iostream>

using namespace std;

#ifndef ANDROIDARCHITECT02_PRIORITYQUEUE_H
#define ANDROIDARCHITECT02_PRIORITYQUEUE_H

template<class E>
class PriorityQueue {
    int count; // 数组的大小，不够时要扩容
    int index = 0; // 当前数据的角标, 根节点的角标是1(左角标2， 右角标3).便于后续计算。
    E *array = NULL; // 存放的数据数组。当做堆。


private:
    // 数据不断往上冒(保证根节点的值最大)。index 新插入item的角标。
    void shiftUp(int index) {
        // 与节点的 父节点做比较, 比父节点大，就交换；否则就结束跳出去。
        // 防止角标越界：index>1
        if(index>1 && array[index] > array[index/2] ) { // array[index/2]是父节点的值。
            // 保证父节点的值，最大。
            swap(array[index], array[index/2] ); // 与父节点交换数据。

            shiftUp(index/2); // 递归。不断与父节点 比较。继续往上冒。
        }
        // 直到array[index] < array[index/2] 不需要往上冒。
    }

    // 从根节点开始，往下调整为大根堆。k是父节点的索引。
    void shiftDown(int k) {
        // 循环实现，从根节点到所有子节点的遍历。
        while(k * 2 <= index) { // 到底部了。
            // 最大指向他的 左孩子
            int max = 2*k;
            // 判断是否有 右孩子. 有 右孩子(max+1 <= index)，且右孩子 大于 左孩子。
            if(max +1 <= index && array[max+1] > array[max]) {
                max = max+1; // 指向右孩子，最大值索引index， 更新max
            }
            // 最大的还是是自己(跟左右孩子比)，跳出去；否则就交换。
            if(array[k] > array[max]) {
                break;
            }
            // 交换：最大的往上冒
            swap(array[k], array[max]);
            // 继续往下走 while，递归。
            k = max;
        }
        // 循环结束了
    }

public:
    PriorityQueue(int count) {
        this->count = count;
        array = new T[count];
    }
    bool isEmpty() { // 是否为空
        return index == 0;
    }

    // 移除item，最大的在第一个位置。
    // 大根堆(最大堆)：父亲 永远比叶子大。
    E pop() { // 出队列
        E max = array[1]; // 移除第一个元素(根元素)。
        // 出队：把最后一个挪到最前面，然后对左右进行判断，那个最大，往上冒。
        // 最终线程最大堆。出队和入队，复杂度log(N)
        array[1] = array[index]; // 最后一个与第一个 [交换]。相当于一次复制。

        index --; // 角标是从1开始的(根节点的角标 == 1)。
        shiftDown(1); // 第一个item， 小的数据往下冒。调整为大根堆（将最大值，作为根节点）。
        return max;
    }

    // 入队列， push完后，最大的在最前面。形成大堆树。
    void push(E e) { // 添加元素
        array[index + 1] = e; // 添加到数组的最后面。
        index++;

        // 不断地调整堆。根父亲比较大小，做交换。将插入的之后一个item，不断往上冒泡(最大值在最上面)。
        shiftUp(index);

        // 打印所有元素。
        for(int i=0; i<index; i++) {
             // 索引从1开始的。所以要+1处理。
             __android_log_print(ANDROID_LOG_ERROR, "TAG", "%d", array[index +1]);
        }
        __android_log_print(ANDROID_LOG_ERROR, "TAG", "----------------");
    }
};



#endif //ANDROIDARCHITECT02_PRIORITYQUEUE_H

// 循环都可以写成迭代；但是迭代不一定能写成循环。
// 不断地调整为大根堆，然后输出根节点。就相当于有序序列了，进而达到排序的目的。
// 堆排序的实现。 优先级队列，输出出来，就是已经排好顺序的。




